# 113.路径总和II
# 给你二叉树的根节点root和一个整数目标和targetSum ，找出所有从根节点到叶子节点路径总和等于给定目标和的路径。
# 叶子节点是指没有子节点的节点。
#
# 示例1：
# 输入：root = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1], targetSum = 22
# 输出：[[5, 4, 11, 2], [5, 8, 4, 5]]
#
# 示例2：
# 输入：root = [1, 2, 3], targetSum = 5
# 输出：[]
#
# 示例3：
# 输入：root = [1, 2], targetSum = 0
# 输出：[]

import sys
sys.setrecursionlimit(1000000)  # 例如这里设置为一百万
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    # 没懂这个东西
    def pathSum(self, root: [TreeNode], targetSum: int):
        res = []
        path = []
        def traver(root,count):

            if not root.left and not root.right:
                if count == 0:
                    res.append(path[:])
                    return
            if not root.left and not root.right:
                return
            if root.left:
                path.append(root.left.val)
                count -= root.left.val
                traver(root.left,count)
                count += root.left.val
                path.pop()
            if root.right:
                path.append(root.right.val)
                count -= root.right.val
                traver(root.right,count)
                count += root.right.val
                path.pop()
            return
        if not root:
            return res
        path.append(root.val)
        traver(root,count=targetSum-root.val)
        return res
if __name__ == '__main__':
    a31 = TreeNode(15)
    a32 = TreeNode(7)
    a22 = TreeNode(20,a31,a32)
    a21 = TreeNode(35)
    a11 = TreeNode(3,a21,a22)
    tmp = Solution()
    aaaa = 38
    res = tmp.pathSum(a11,aaaa)
    # targetSum = 23
    # res = tmp.hasPathSum(a11,targetSum)
    print(res)
